{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "48970ca0",
      "metadata": {},
      "source": [
        "# NonlinearConjugateGradientOptimizer\n",
        "\n",
        "## Overview\n",
        "\n",
        "The `NonlinearConjugateGradientOptimizer` class in GTSAM is an implementation of the nonlinear conjugate gradient method for optimizing nonlinear functions. This optimizer is particularly useful for solving large-scale optimization problems where the Hessian matrix is not easily computed or stored. The conjugate gradient method is an iterative algorithm that seeks to find the minimum of a function by following a series of conjugate directions.\n",
        "\n",
        "The nonlinear conjugate gradient method seeks to minimize a nonlinear function $f(x)$ by iteratively updating the solution $x_k$ according to:\n",
        "\n",
        "$$ x_{k+1} = x_k + \\alpha_k p_k $$\n",
        "\n",
        "where $p_k$ is the search direction and $\\alpha_k$ is the step size determined by a line search. The search direction $p_k$ is computed using the gradient of the function and a conjugate gradient update formula, such as the Fletcher-Reeves or Polak-Ribiere formulas:\n",
        "\n",
        "- **Fletcher-Reeves**: \n",
        "  $$ \\beta_k^{FR} = \\frac{\\nabla f(x_{k+1})^T \\nabla f(x_{k+1})}{\\nabla f(x_k)^T \\nabla f(x_k)} $$\n",
        "  \n",
        "- **Polak-Ribiere**: \n",
        "  $$ \\beta_k^{PR} = \\frac{\\nabla f(x_{k+1})^T (\\nabla f(x_{k+1}) - \\nabla f(x_k))}{\\nabla f(x_k)^T \\nabla f(x_k)} $$\n",
        "\n",
        "The choice of $\\beta_k$ affects the convergence properties of the algorithm.\n",
        "\n",
        "Key features:\n",
        "\n",
        "- **Optimization Method**: Implements the nonlinear conjugate gradient method, which is an extension of the linear conjugate gradient method to nonlinear optimization problems.\n",
        "- **Efficiency**: Suitable for large-scale problems due to its iterative nature and reduced memory requirements compared to methods that require the Hessian matrix.\n",
        "- **Flexibility**: Can be used with various line search strategies and conjugate gradient update formulas.\n",
        "\n",
        "## Key Methods\n",
        "\n",
        "Please see the base class [NonlinearOptimizer.ipynb](NonlinearOptimizer.ipynb).\n",
        "\n",
        "## Parameters\n",
        "\n",
        "The nonlinear conjugate gradient optimizer uses the standard optimization parameters inherited from `NonlinearOptimizerParams`, which include:\n",
        "\n",
        "- Maximum iterations\n",
        "- Relative and absolute error thresholds\n",
        "- Error function verbosity\n",
        "- Linear solver type\n",
        "\n",
        "## Usage Notes\n",
        "\n",
        "- The `NonlinearConjugateGradientOptimizer` is most effective when the problem size is large and the computation of the Hessian is impractical.\n",
        "- Users should choose an appropriate line search method and conjugate gradient update formula based on the specific characteristics of their optimization problem.\n",
        "- Monitoring the error and values during optimization can provide insights into the convergence behavior and help diagnose potential issues.\n",
        "\n",
        "## Files\n",
        "\n",
        "- [NonlinearConjugateGradientOptimizer.h](https://github.com/borglab/gtsam/blob/develop/gtsam/nonlinear/NonlinearConjugateGradientOptimizer.h)\n",
        "- [NonlinearConjugateGradientOptimizer.cpp](https://github.com/borglab/gtsam/blob/develop/gtsam/nonlinear/NonlinearConjugateGradientOptimizer.cpp)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "colab_button",
      "metadata": {},
      "source": [
        "<a href=\"https://colab.research.google.com/github/borglab/gtsam/blob/develop/gtsam/nonlinear/doc/NonlinearConjugateGradientOptimizer.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "license_cell",
      "metadata": {
        "tags": [
          "remove-cell"
        ]
      },
      "source": [
        "GTSAM Copyright 2010-2022, Georgia Tech Research Corporation,\nAtlanta, Georgia 30332-0415\nAll Rights Reserved\n\nAuthors: Frank Dellaert, et al. (see THANKS for the full author list)\n\nSee LICENSE for the license information"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "colab_import",
      "metadata": {
        "tags": [
          "remove-cell"
        ]
      },
      "outputs": [],
      "source": [
        "try:\n    import google.colab\n    %pip install --quiet gtsam-develop\nexcept ImportError:\n    pass"
      ]
    }
  ],
  "metadata": {
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}